package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         255,
		Discription: "验证是否为二叉搜索树的前序遍历",
		Level:       2,
		Labels: map[string]int{
			"二叉树": 1,
			"二叉搜搜树": 1,
			"递归": 1,
		},
	})
}

func VerifyPreorder(preorder []int) bool {
	//<=1节点的子树无需判断
	if len(preorder) <= 1 {
		return true
	}

	//找到右子树的根节点
	i := 1
	for ; i < len(preorder); i++ {
		if preorder[i] > preorder[0] {
			break
		}
	}

	//右子树根节点之后有小于根节点的，说明非法
	for j := i + 1; j < len(preorder); j++ {
		if preorder[j] < preorder[0] {
			return false
		}
	}

	//递归验证左子树和右子树
	return VerifyPreorder(preorder[1:i]) && VerifyPreorder(preorder[i:])
}